//------------------------------
// 解法一
//------------------------------
package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {

	public static void main(String[] args) {

		Node root = new Node(1);
		root.left = new Node(2);
		root.right = new Node(3);
		root.left.left = new Node(4);
		root.left.right = new Node(5);
		root.left.left.left = new Node(6);
		root.left.left.right = new Node(7);
		root.left.right.left = new Node(8);
		root.left.right.right = new Node(9);
		System.out.println(maxWidth(root));
	}

	public static int maxWidth(Node root) {

		// 1.参数校验 //
		Objects.requireNonNull(root, "参数root不能为null");
		// 2.获取树的高度 //
		int[] widthArr = new int[high(root)];
		// 3.计算各层节点数级宽度 //
		for (int i = 0; i < widthArr.length; i++) {
			widthArr[i] = levelSize(root, i + 1);
		}
		// 4.找出最大宽度 //
		System.out.println(Arrays.toString(widthArr));
		int max = widthArr[0];
		for (int i = 1; i < widthArr.length; i++) {
			if (max < widthArr[i]) {
				max = widthArr[i];
			}
		}
		return max;
	}

	private static int high(Node node) {

		if (node == null) {
			return 0;
		}
		int h1 = high(node.left) + 1;
		int h2 = high(node.right) + 1;
		return h1 > h2 ? h1 : h2;
	}

	private static int levelSize(Node root, int k) {

		if (k <= 0) {
			throw new IllegalArgumentException("参数k必须大于0");
		}
		return levelSize0(root, k);
	}

	private static int levelSize0(Node node, int k) {

		if (node == null) {
			return 0;
		}
		if (k == 1) {
			return 1;
		}
		return levelSize0(node.left, k - 1) + levelSize0(node.right, k - 1);
	}
}

class Node {

	public Node left;
	public Node right;
	public int data;

	public Node(int data) {
		this.data = data;
	}
}

//------------------------------
// 解法二
//------------------------------

package cn.edu.jxau.test;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class Main {

	public static void main(String[] args) {

		Node root = new Node(1);
		root.left = new Node(2);
		root.right = new Node(3);
		root.left.left = new Node(4);
		root.left.right = new Node(5);
		root.left.left.left = new Node(6);
		root.left.left.right = new Node(7);
		root.left.right.left = new Node(8);
		root.left.right.right = new Node(9);
		System.out.println(maxWidth(root));
	}

	public static int maxWidth(Node root) {

		// 1.参数校验 //
		Objects.requireNonNull(root, "参数root不能为null");
		// 2.层次遍历 //
		int maxWidth = 0;
		Queue<Node> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			int levelSize = queue.size();
			while (levelSize > 0) {
				Node node = queue.poll();
				levelSize--;
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
			maxWidth = maxWidth > queue.size() ? maxWidth : queue.size();
		}
		return maxWidth;
	}
}

class Node {

	public Node left;
	public Node right;
	public int data;

	public Node(int data) {
		this.data = data;
	}
}